# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 12_min_stack.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/26 13:55
------------------------------------------
    最小栈
    实现一个栈，该栈7有出栈(pop)、入栈(push)、取最小元素(get_min)三个方法
"""


class MinStack:
    def __init__(self):
        self.main_stack = []
        self.min_stack = []

    def push(self, element):
        self.main_stack.append(element)

        # 若辅助栈为空，或者新元素的的值小于或等于辅助栈栈顶元素的值，则将新元素压入辅助栈
        if not self.min_stack or element <= self.min_stack[len(self.min_stack) - 1]:
            self.min_stack.append(element)

    def pop(self):
        # 如果出栈元素和辅助栈栈顶元素的值相等，则辅助栈的栈顶元素也出栈
        if self.min_stack and self.main_stack[len(self.main_stack) - 1] == self.min_stack[len(self.min_stack) - 1]:
            self.min_stack.pop()

        if self.main_stack:
            return self.main_stack.pop()

        else:
            return None

    def get_min(self):
        if not self.min_stack:
            return None

        return self.min_stack[len(self.min_stack) - 1]


def demo():
    my_stack = MinStack()
    my_stack.push(4)
    my_stack.push(9)
    my_stack.push(7)
    my_stack.push(3)
    my_stack.push(8)
    my_stack.push(5)
    print(my_stack.get_min())

    print(my_stack.pop())
    print(my_stack.pop())
    print(my_stack.pop())
    print(my_stack.get_min())


if __name__ == '__main__':
    demo()
